#include <bits/stdc++.h>
using namespace std;

/*
3202. 找出有效子序列的最大长度 II
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个整数数组 nums 和一个 正 整数 k 。
nums 的一个 子序列 sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列 ：

(sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % k
返回 nums 的 最长有效子序列 的长度。
 

示例 1：

输入：nums = [1,2,3,4,5], k = 2

输出：5

解释：

最长有效子序列是 [1, 2, 3, 4, 5] 。

示例 2：

输入：nums = [1,4,2,3,1,4], k = 3

输出：4

解释：

最长有效子序列是 [1, 4, 1, 4] 。

 

提示：

2 <= nums.length <= 103
1 <= nums[i] <= 107
1 <= k <= 103
*/

// 法一
class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        // dp 表示以当前余数为结尾 且与下一个数的余数组成有效子序列的最大长度
        vector<vector<int>> dp(k, vector<int>(k, 0));
        int ans = 0;
        for (const auto& num : nums) {
            int x = num % k;
            if (x < 0) x += k;  // 处理负数取模

            for (int y = 0; y < k; ++y) {
                // 当一个余数为x 前一个余数为y 当前数接到以y结尾 且下一个为x的子序列后面
                // dp len + 1
                dp[y][x] = max(dp[y][x], dp[x][y] + 1);
                ans = max(ans, dp[y][x]);
            }
        }
        return ans;
    }
};

// 法二
class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        // l[i][r] 表示当前以余数i结尾，且相邻元素余数和模k等于(r+i)%k的最长子序列长度
        int l[k][k];
        int ans = 0;
        memset(l, 0, sizeof(l)); // 初始化为0
        
        for (auto &num : nums) {
            int r = num % k; // 当前元素的余数
            
            // 遍历所有可能的前一个余数i
            for (int i = 0; i < k; ++i) {
                // 计算需要的前一个余数和当前余数的和模k的值
                // 即如果前一个余数是i，那么需要满足(i + r) % k == target
                // 因此前一个余数i和其前一个余数的和模k必须等于(target - r + k) % k
                
                // 更新l[i][r]为以下两者的较大值：
                // 1. 当前值l[i][r]
                // 2. l[i][(i - r + k) % k] + 1，即接上当前余数r后的新长度
                l[i][r] = max(l[i][(i - r + k) % k] + 1, l[i][r]);
                
                // 更新全局最大长度
                ans = max(ans, l[i][r]);
            }
        }
        
        return ans;
    }
};

// 法三
// 法二变种
class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        int n = nums.size();
        // dp[i][t] 表示以索引i结尾且相邻元素和模k等于t的最长子序列长度
        int dp[n][k];
        int m = 0; // 记录全局最长子序列长度
        
        // 初始化dp数组，每个元素自身构成长度为1的子序列
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < k; j++) {
                dp[i][j] = 1;
            }
        }
        
        // 遍历每个元素作为子序列的结尾
        for(int i = 0; i < n; i++) {
            // 检查所有可能的前一个元素j
            for(int j = 0; j < i; j++) {
                // 计算当前元素和前一个元素的和模k的值
                int t = (nums[i] + nums[j]) % k;
                // 如果将当前元素i接到以j结尾且和模为t的子序列后能更长，则更新
                dp[i][t] = max(dp[i][t], dp[j][t] + 1);
                // 更新全局最长长度
                m = max(m, dp[i][t]);
            }
        }
        
        return m;
    }
};